/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: user
 * Date: 2023-10-11
 * Time: 18:50
 */

    */public class test1011 {
        /**
         * @Author 12629
         * @Description：
         */
        public class Sort {

            /**
             * 时间复杂度：
             *    最坏情况下：O(n^2)
             *    最好情况下：O(n)   当数据越有序 排序越快
             *    适用于：待排序序列 已经基本上趋于有序了！
             * 空间复杂度：
             *    O(1)
             * 稳定性：
             *    稳定的
             * @param array
             */
            public static void insertSort(int[] array) {
                for (int i = 1; i < array.length; i++) {
                    int tmp = array[i];
                    int j = i-1;
                    for (; j >= 0 ; j--) {
                        //这里加不加等号  和稳定有关系
                        // 但是：本身就是一个稳定的排序 可以实现为不稳定的排序
                        // 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的
                        if(array[j] > tmp) {
                            array[j+1] = array[j];
                        }else {
                            //array[j+1] = tmp;
                            break;
                        }
                    }
                    array[j+1] = tmp;
                }
            }

            //希尔排序
            public static void shellSort(int[] array) {
                int gap = array.length;
                while (gap > 1) {
                    gap /= 2;
                    shell(array,gap);
                }
            }

            /**
             * 对每组进行插入排序
             * @param array
             * @param gap
             */
            public static void shell(int[] array,int gap) {
                for (int i = gap; i < array.length; i++) {
                    int tmp = array[i];
                    int j = i-gap;
                    for (; j >= 0 ; j-=gap) {
                        //这里加不加等号  和稳定有关系
                        // 但是：本身就是一个稳定的排序 可以实现为不稳定的排序
                        // 但是 本身就是一个不稳定的排序 是不可能变成一个稳定的排序的
                        if(array[j] > tmp) {
                            array[j+gap] = array[j];
                        }else {
                            //array[j+1] = tmp;
                            break;
                        }
                    }
                    array[j+gap] = tmp;
                }
            }

        }

